package demo;

import java.util.Arrays;

public class QuickSort {
    public static void swap(int[]arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    private static void quickSort(int[]arr){
        quickSortRange(arr,0,arr.length-1);

    }
    private static void quickSortRange(int[]arr,int formIndex,int toIndex){
        //求出要求数组区间的元素个数
        int size=toIndex-formIndex+1;
        if(size<=1){
            return;
        }
        int pivotIdx=partition3(arr,formIndex,toIndex);
        quickSortRange(arr,formIndex,pivotIdx-1);
        quickSortRange(arr,pivotIdx+1,toIndex);
    }
    //partition Hoare法
    private static int partition(int[]arr,int formIndex,int toIndex){

        int lefIdx=formIndex;
        int rigIdx=toIndex;

        int pivot=arr[toIndex];

        while(rigIdx>lefIdx){
            while(rigIdx>lefIdx&&arr[lefIdx]<=pivot){
                lefIdx++;
            }
            //此循环结束说明找到了大于基准值的元素
            while(rigIdx>lefIdx&&arr[rigIdx]>=pivot){
                rigIdx--;
            }
            //此循环结束说明找到了小于基准值的元素
            swap(arr,lefIdx,rigIdx);

        }
        swap(arr,lefIdx,toIndex);
        return lefIdx;
    }
    //partition挖坑法
    private static int partition2(int[]arr,int formIndex,int toIndex){
        int leftIdx=formIndex;
        int rightIdx=toIndex;


        int pivot=arr[toIndex];
        while(leftIdx<rightIdx){
            while(leftIdx<rightIdx&&arr[leftIdx]<=pivot){
                leftIdx++;
            }

            arr[rightIdx]=arr[leftIdx];

            while(leftIdx<rightIdx&&arr[rightIdx]>=pivot){
                rightIdx--;
             }

            arr[leftIdx]=arr[rightIdx];
        }
        arr[leftIdx]=pivot;
        return leftIdx;
    }
    //partition前后指针法
    private static int partition3(int[]arr,int formIdx,int toIdx){
        int leftIdx=formIdx;
        int rightIdx=formIdx;
        int pivot=arr[toIdx];
        while(rightIdx<toIdx){
            if(arr[rightIdx]>=pivot){
                rightIdx++;
            }else{
                swap(arr,leftIdx,rightIdx);
                leftIdx++;
                rightIdx++;
            }
        }
        arr[leftIdx]=pivot;
        return leftIdx;

    }




    public static void main(String[] args) {
        int[]arr={1,5,2,4,8,3,7,10};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));

    }
}
